#include <iostream>
#include <vector>
using namespace std;

class Solution {
        const int MOD = 1000000007;
        vector<vector<int>> hum;
        int max_hats = 0;
        int cnt = 0;
        int ways(int status, int n, vector<vector<int>> &dp)
        {
                if(status == ((1 << cnt) - 1)){
                        return 1;
                }

                if(n > max_hats){
                        return 0;
                }

                if(dp[status][n] != -1){
                        return dp[status][n];
                }

                int ans = ways(status, n + 1, dp) % MOD;

                for(auto m : hum[n]){
                        if((status & (1 << m)) == 0){
                                ans = (ans + ways(status | (1 << m), n + 1, dp))%MOD;
                        }
                }

                return dp[status][n] = ans;
        }
    public:
	int numberWays(vector<vector<int>> &hats)
	{
                cnt = hats.size();
                hum.resize(41);
                for(int i = 0; i < cnt; i++){
                        for(auto h : hats[i]){
                                max_hats = max(max_hats, h);
                                hum[h].push_back(i);
                        }
                }

                vector<vector<int>> dp(1 << cnt, vector<int>(max_hats + 1, -1));

                return ways(0, 1, dp);
	}
};

int main()
{
        vector<vector<int>> hats = {{3,4},{4,5},{5}};
        cout << Solution().numberWays(hats) << endl;
        return 0;
}